/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function (deadends, target) {
  if(deadends.includes("0000")) return -1;
  let visited = new Set();
  let queue = [];
  queue.push("0000");
  let count = 0;
  while (queue.length) {
    let size = queue.length;
    while (size--) {
      let str = queue.shift();
      for (let i = 0; i < 4; i++) {
        let char = str[i];
        let strAdd = str.substring(0, i) + (char == '9' ? '0' : (parseInt(char) + 1).toString()) + str.substring(i + 1);
        let strSub = str.substring(0, i) + (char == '0' ? '9' : (parseInt(char) - 1).toString()) + str.substring(i + 1);
        if (str == target) return count;
        if (!deadends.includes(strAdd) && !visited.has(strAdd)) {
          queue.push(strAdd);
          visited.add(strAdd);
        }
        if (!deadends.includes(strSub) && !visited.has(strSub)) {
          queue.push(strSub);
          visited.add(strSub);
        }
      }
    }
    count++;
  }
  return -1;
};
let deadends = ["0201", "0101", "0102", "1212", "2002"],
  target = "0202";
console.log(openLock(deadends, target));
deadends = ["8888"], target = "0009";
console.log(openLock(deadends, target));
deadends = ["8887", "8889", "8878", "8898", "8788", "8988", "7888", "9888"], target = "8888";
console.log(openLock(deadends, target));
